#include <cstdio>
#include <cstring>
#include <vector>

typedef unsigned long long ull;

const int N = 1e5 + 5, M = 105, mod = 1e9 + 7;

int t, n, m, f[M][(1 << 4) + 1];
int num[N], sum[N], fac[N], inv[N], pri[M] = {2, 3, 5, 7}, tot;
std::vector<int> vec[M];
bool vis[M];

inline int qpow(ull base, int exp) {
  ull res = 1;
  while (exp) {
    if (exp & 1) res = res * base % mod;
    base = base * base % mod;
    exp >>= 1;
  }
  return res;
}

inline ull C(int n, int m) {
  return (ull)fac[n] * inv[n - m] % mod * inv[m] % mod;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("mod.in", "r", stdin);
  freopen("mod.out", "w", stdout);
#endif
#endif

  scanf("%d", &t);
  fac[0] = 1;
  for (int i = 1; i < N; ++i) fac[i] = (ull)fac[i - 1] * i % mod;
  inv[N - 1] = qpow(fac[N - 1], mod - 2);
  for (int i = N - 2; ~i; --i) inv[i] = (ull)inv[i + 1] * (i + 1) % mod;
  for (int i = 2; i < M; ++i) {
    if (!vis[i]) {
      if (i < 10) num[i] |= 1 << tot;
      pri[tot++] = i;
    }
    for (int j = 0; j < tot && pri[j] * i < M; ++j) {
      vis[i * pri[j]] = true;
      num[i * pri[j]] = num[i] | num[pri[j]];
      if (i % pri[j] == 0) break;
    }
  }
  while (t--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) vec[i].clear();
    for (int i = 2; i <= m; ++i) {
      int _i = i;
      for (int j = 0; j < 4; ++j) {
        if (_i % pri[j] == 0) {
          num[i] |= 1 << j;
          while (_i % pri[j] == 0) _i /= pri[j];
        }
      }
      vec[_i].emplace_back(i);
    }
    int cnt = 1;
    memset(sum, 0, sizeof(sum));
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (auto i : vec[1]) {
      for (int j = 0; j < 4; ++j) {
        for (int k = 0; k < 1 << 4; ++k) {
          if (!(k & num[i]))
            if ((f[j + 1][k | num[i]] += f[j][k]) >= mod)
              f[j + 1][k | num[i]] -= mod;
        }
      }
    }
    for (int i = 11; i <= m; ++i) {
      if (!vec[i].empty()) {
        ++cnt;
        for (int j = 30; ~j; --j) {
          for (int k = 0; k < 1 << 4; ++k) {
            for (auto h : vec[i])
              if (!(k & num[h]))
                if ((f[j + 1][k | num[h]] += f[j][k]) >= mod)
                  f[j + 1][k | num[h]] -= mod;
          }
        }
      }
    }
    ull ans = 0;
    for (int i = 0; i <= std::min(n, 25); ++i) {
      for (int j = 0; j < 1 << 4; ++j) {
        sum[i] += f[i][j];
        if (sum[i] >= mod) sum[i] -= mod;
      }
    }
    for (int i = 0; i <= std::min(n, 25); ++i) {
      ans += (ull)sum[i] * fac[i] % mod * C(n, n - i) % mod;
      if (ans >= mod) ans -= mod;
    }
    printf("%llu\n", ans);
  }
  return 0;
}